package com.lw.leetcode.binary.b;

/**
 * Created with IntelliJ IDEA.
 * 34. 在排序数组中查找元素的第一个和最后一个位置
 *
 * @author liw
 * @version 1.0
 * @date 2021/10/14 13:01
 */
public class SearchRange {
    public int[] searchRange(int[] nums, int target) {
        int length = nums.length;
        if (length == 0) {
            return new int[]{-1, -1};
        }
        if (length == 1) {
            if (nums[0] == target) {
                return new int[]{0, 0};
            } else {
                return new int[]{-1, -1};
            }
        }
        int x = aa(nums, target);
        int y = bb(nums, target);
        return new int[]{x, y};
    }

    private static int aa(int[] nums, int target) {
        int st = 0;
        int end = nums.length - 1;
        int m;

        while (st <= end) {
            m = (st + end) / 2;
            if (target < nums[m]) {
                end = m - 1;
            } else if (target > nums[m]) {
                st = m + 1;
            } else {
                if (m > 0 && target == nums[m - 1]) {
                    end = m - 1;
                } else {
                    return m;
                }
            }
        }
        return -1;
    }

    private static int bb(int[] nums, int target) {
        int st = 0;
        int end = nums.length - 1;
        int length = nums.length - 1;
        int m;
        while (st <= end) {
            m = (st + end) / 2;
            if (target < nums[m]) {
                end = m - 1;
            } else if (target > nums[m]) {
                st = m + 1;
            } else {
                if (m < length && target == nums[m + 1]) {
                    st = m + 1;
                } else {
                    return m;
                }
            }
        }
        return -1;
    }

}
